package leetcode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class LeetCodeMain92 {
    public String decodeString(String s) {
        Stack<Character> stack=new Stack<>();
        int length=s.length();
        String str="";
        String s1="";
        for (int i = 0; i < length; i++) {
            char ch=s.charAt(i);
            stack.push(ch);
        }
        int left=0;
        int right=0;
        while (!stack.isEmpty()){
            char ch=stack.pop();
            if (ch==']'){
                right++;
                if (s1!=null&&!"".equals(s1)){
                    str = s1 + str;
                    s1 = "";
                }
            }
            if (ch=='['){
                left++;
            }
            if (Character.isAlphabetic(ch)) {
                s1 = ch +s1;
            }
            if (right>=left&&left!=0&&right!=0&&Character.isDigit(ch)){
                int count=ch-'0';
                String s2="";
                for (int i = 1; i <= count&&!"".equals(s1); i++) {
                    s2+=s1;
                }
                left--;
                right--;
                s1=s2;
                if ((!stack.isEmpty()&&stack.peek()==']')){
                    str=s2+str;
                    s1="";
                }

            }
        }
        if (s1!=null&&!"".equals(s1)){
            str=s1+str;
        }
        return str;
    }

    public static void main(String[] args) {
        LeetCodeMain92 main92=new LeetCodeMain92();
        System.out.println(main92.decodeString( "10[a]"));
    }
    public int count=0;
    public void DFS(TreeNode root,int sum,int targetSum){
        if (root==null){
            return;
        }
        sum+=root.val;
        DFS(root.left, sum, targetSum);
        DFS(root.right, sum, targetSum);
        if (sum==targetSum){
            count++;
        }
        sum-=root.val;
    }
    public int pathSum(TreeNode root, int targetSum) {
        //先层次遍历
//        Deque<TreeNode> deque=new LinkedList<>();
//        if (root==null){
//            return count;
//        }
//        deque.add(root);
//        while (!deque.isEmpty()){
//            int size=deque.size();
//            while (size>0){
//                TreeNode node=deque.poll();
//                if (node.left!=null){
//                    deque.add(node.left);
//                }
//                if (node.right!=null){
//                    deque.add(node.right);
//                }
//                DFS(node,0,targetSum);
//                size--;
//            }
//        }
        //全递归
        if (root==null){
            return 0;
        }
        DFS(root,0,targetSum);
        pathSum(root.left,targetSum);
        pathSum(root.right,targetSum);
        return count;
    }
}
